//给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。 
//
// 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。 
//
// 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 
//
// 
//
// 示例： 
//
// 
//输入：[[1,2], [2,3], [3,4]]
//输出：2
//解释：最长的数对链是 [1,2] -> [3,4]
// 
//
// 
//
// 提示： 
//
// 
// 给出数对的个数在 [1, 1000] 范围内。 
// 
//
// Related Topics 贪心 数组 动态规划 排序 👍 262 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _646_MaximumLengthOfPairChain {
    public static void main(String[] args) {
        Solution solution = new _646_MaximumLengthOfPairChain().new Solution();
        int[][] pairs = {{-6, 9}, {1, 6}, {8, 10}, {-1, 4}, {-6, -2}, {-9, 8}, {-5, 3}, {0, 3}};
        System.out.println(solution.findLongestChain(pairs));
    }

    class Solution {
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
            int cur = Integer.MIN_VALUE;
            int res = 0;
            for (int[] pair : pairs) {
                if (cur < pair[0]) {
                    cur = pair[1];
                    res++;
                }
            }
            return res;
        }
    }

    class Solution2 {
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
            List<Integer> arr = new ArrayList<>();
            for (int[] pair : pairs) {
                int x = pair[0];
                int y = pair[1];
                if (arr.isEmpty() || x > arr.get(arr.size() - 1)) {
                    arr.add(y);
                } else {
                    int idx = binarySearch(arr, x);
                    arr.set(idx, Math.min(arr.get(idx), y));
                }
            }
            return arr.size();
        }

        private int binarySearch(List<Integer> arr, int x) {
            int low = 0;
            int high = arr.size() - 1;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (arr.get(mid) >= x) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (a, b) -> {
                int res1 = a[0] - b[0];
                int res2 = res1 == 0 ? a[1] - b[1] : res1;
                return res2;
            });
            int n = pairs.length;
            int[] dp = new int[n];
            Arrays.fill(dp, 1);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (pairs[i][0] > pairs[j][1]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp[n - 1];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}